\input{euler.tex}
\usepackage{graphicx}

\begin{document}

\problem[327]{Rooms of Doom}

$R$ rooms are connected consecutively by $(R-1)$ doors. In addition, there is one door to enter the first room and another door to exit of the last room. One card will be consumed to pass one of the doors in either direction, and the door will immediately be closed after you pass it. You are allowed to carry at most $C$ cards when passing any door, but can store unlimited number of cards in each room. A dispensing machine stands by the entrance outside the first room from which an unlimited number of cards may be retrieved. The problem is to find the minimum number of cards required to pass through all the rooms.
\begin{center}
\includegraphics[height=16mm]{p327_1.png}
\end{center}

Let $C$ be the maximum number of cards which can be carried at any time.

Let $R$ be the number of rooms to travel through.

Let $M(C,R)$ be the minimum number of cards required from the dispensing machine to travel through $R$ rooms carrying up to a maximum of $C$ cards at any time.

For example, $M(3,6)=123$ and $M(4,6)=23$. Also, $\sum M(C,6)=146$ for $3 \le C \le 4$, and $\sum M(C,10)=10382$ for $3 \le C \le 10$.

Find $\sum M(C,30)$ for $3 \le C \le 40$.

\solution

We solve the problem using a recursive approach. Let $N(k; C)$ be the minimum number of cards one needs to have in the current room so that he will have $k$ cards after he moves into the next room. Obviously, if $k+1 \le C$, one can simply carry $(k+1)$ cards, consume one card to open the door, and enter the next room with $k$ cards.

If $k+1 > C$, then one needs to transfer cards to the next room in chunks. Each time, he can carry $C$ cards, consume one card to open the door, leave $(C-2)$ cards in the next room, and consume the last card to come back. After one such round, he is left with $k-(C-2)$ cards to transfer. One repeats this $r$ rounds until $k-r(C-2)+1 \le C$, when he can carry $k-r(C-2)$ cards into the next room (using one card to open the door) without returning. The total number of cards needed before the final round is $rC$.

Writing the above reasoning in formula, we have
\[
N(k; C) = rC + k-r(C-2)+1 = k + 2r + 1 ,
\]
where 
\[
r = \max\left(0, \lceil (k+1-C)/(C-2) \rceil \right) = \max(0, \lfloor (k-2)/(C-2) \rfloor ) .
\]
It then follows that the minimum number of cards needed to pass $R$ rooms is equal to the minimum number of cards needed before entering the first room so that one will be left with the minimum number of cards to pass $(R-1)$ rooms. That is,
\[
M(C,R) = N(M(C,R-1); C) .
\]
The starting condition $M(C,0) = 1$. This formula allows us to compute all $M(C, R)$ recursively.

\complexity

Time complexity: $\BigO(CR)$.

Space complexity: $\BigO(1)$.

\answer

34315549139516

\end{document} 